The present invention relates to signal analyzers and, more particularly, to a novel signal processing method and system that analyzes the frequency (spectral) characteristics of a signal in electrical form through a technique that uses the Multidimensional Discrete Fourier Transform (MDFT) in conjunction with the internal structural properties of the Discrete Fourier Transform (DFT).
The frequency (spectral) content of a signal is an important parameter in numerous applications such as radar and sonar signal processing, speech analysis and synthesis, meteorological measurements, vibration analysis, and so forth. In a Doppler radar system, for example, the echo or return signal contains various frequency components. These frequency components are typically analyzed by "Fourier analysis" techniques to provide information as to the existence of moving and stationary objects and characteristics such as the speed of the objects.
Fourier analysis essentially breaks the signal down into various frequency components so that a complex signal can be represented by a series of simple or fundamental frequencies. The simple frequencies can then be used to reconstruct the events that are causing or generating the complex frequency spectrum of the signal under consideration.
A continuous signal can be decomposed into sets of sinusoidal functions by the Fourier Transform: ##EQU1## in which G(.mu.) is called the frequency spectrum of the signal f(t). The Fourier Transform, therefore, transforms a signal from the time domain in which the signal is expressed as a function of time into the frequency domain in which the signal is expressed as a function of frequency.
Frequency analysis techniques have advanced over the years from mere separation of frequencies by analog filtering to present day techniques involving digital analysis. For digital analysis, the signal to be processed is quantitized by a suitable sampling or other digitizing process.
When the continuous signal is digitized, the Fourier Transform cannot be used to represent the frequency spectrum of the digitized signal due to the discrete nature of the digitized signal. However, a discrete approximation derived from the Fourier Transform can be used to transform digitized signals from the time domain into the frequency domain. This discrete approximation is referred to as the Discrete Fourier Transform (DFT).
A digitized signal can be decomposed into sets of sinusoidal functions by the Discrete Fourier Transform, the k-th term of which is: ##EQU2## where N represents the total number of digitized samples taken of the continuous time domain signal f(t); n represents the numbering of the digitized samples of the signal f(t); and a.sub.n represents the digitized samples of the signal f(t). This Discrete Fourier Transform is termed an N-point transform since N digitized samples are transformed from the time domain into the frequency domain.
The larger the total number of digitized samples taken of the continuous signal, the closer the digitized time domain signal represents the continuous time domain signal, and the closer the Discrete Fourier Transform of the digitized signal approaches the Fourier Transform of the continuous time domain signal. Therefore, the digital samples may number in the hundreds or even thousands in systems requiring high precision. Consequently, numerous additions, subtractions and multiplications must be performed by a digital processor in order to obtain digital numbers which are indicative of the frequency spectrum of the continuous time domain signal.
A single multiplication typically takes much more time to perform than a single addition or subtraction. Moreover, each multiplication in the DFT generally involves multiplying complex numbers, i.e., numbers containing both a real and an imaginary component. Such complex multiplication further increases the time, and the hardware, required to carry out each multiplication. Thus, the speed at which a particular processor processes data is determined in large part by the number of multiplications the particular processor must perform.
The total amount of hardware required to perform the numerous additions, subtractions and multiplications in an N-point DFT processor can be reduced by cascading an L.sub.1 -point DFT processor stage and an L.sub.2 -point DFT processor stage where N=L.sub.1.L.sub.2. In general, a phase shifter or "twiddle factor" multiplier is required between each stage. But if L.sub.1 and L.sub.2 are mutually prime numbers (i.e., if L.sub.1 and L.sub.2 do not contain any common factors), then an interstage twiddle factor multiplier is not required. What is required, however, are data rotators which suitably reorder the data before the data enters each stage. Thus one type of hardware is traded for another.
It is known that the total amount of hardware required to perform the numerous additions, subtractions and multiplications in an N-point DFT processor stage can also be reduced by requiring the number of data points processed by the stage to be a power of two and then using what is referred to as a Fast Fourier Transform (FFT) technique to calculate the DFT. Thus constrained, N=2.sup.a where a is an integer.
The total amount of hardware required to perform the numerous additions, subtractions and multiplications in an N-point DFT processor stage has also been reduced by requiring N to be the product of certain small prime numbers. Using group theoretic properties of numbers, Shmuel Winograd recently discovered that the computation of an N-point DFT can be converted into a cyclic convolution when the integer N has certain properties. (Winograd, "A New Method For Computing DFT," 1977 IEEE International Convention on Acoustics, Speech and Signal Processing, pp. 366-68).
Using Winograd's discovery and the Chinese Remainder Theorem For Polynomials, it is possible to reduce the number of multipliers required to compute an N-point DFT when N is the product of samll prime numbers. When N is the product of certain small prime numbers, the number of multipliers can be reduced still further.
As in the FFT approach the Winograd Discrete Fourier Transform (WDFT) approach requires multipliers within each processor stage. In general, these intrastage multipliers are complex. However, using the WDFT approach certain small prime numbers are found to exist for which the intrastage multipliers are either real or imaginary but never complex. Thus for certain small prime numbers, the number of multiplications required to be performed, and the corresponding hardware to carry out the multiplications, are reduced.
Numerous approaches to implementing Discrete Fourier Transform signal processors have been employed. The fastest known processors employ Fast Fourier Transform mechanizations. The speed of the known processors is limited by the number of multiplications the particular processor must perform. For example, the FFT processor disclosed in U.S. Pat. No. 3,783,258 transforms 4096 complex points into Fourier coefficients in about 10 milliseconds, and the FFT processor disclosed in U.S. Pat. No. 3,920,978 transforms 1024 points in about 25 milliseconds. Other examples of the prior art approaches to this type of signal processing are included in U.S. Pat. Nos. 3,899,667; 3,777,131; 3,778,604 and 3,952,186.
The fastest known prior art TTL technology processor processes data at approximately a 6 MHz complex signal data rate or a real signal data processing rate of 12 MHz. However, there may be situations in which a real signal data processing rate of 16 MHz or higher may be desirable.
For example, in a typical Doppler radar application, 100 nanosecond pulses of energy may be transmitted at 500 nanosecond intervals. In order to locate and process the return energy, the interval between successive pulses is divided into four intervals called range cells and a predetermined number of samples are taken in each range cell (e.g., 120 samples). Since a target will move only slightly in range from pulse to pulse, e.g., a target moving at 10,000 ft./sec. will move 0.005 ft. in one interpulse period, data can be collected from corresponding range cells in successive interpulse period in order to perform a frequency analysis.
The data collected over a predetermined time interval such as 60 microseconds is reordered so that all the data from the same range cells is grouped together. With the exemplary figures above, therefore, there are four sets of 120 data points (samples) to independently process. For a particular range cell, there is a new piece of complex data every 500 nanoseconds (a 2 MHz complex data rate). Thus, there is a need to process data at a 4 MHz real data rate and since there are four such sets of data collected, the overall real data rate is 16 MHz.
In other words, a typical frequency analysis application may require processing signals in sets of 480 complex data points, with each set representing 120 discrete samples in each of four successive cells. If 480 complex data points are to be processed every 60 microseconds, and if each complex data point has a real and an imaginary part, then the overall real signal data processing rate is 16 MHz. The data therefore must be processed at a 4 MHz real signal data rate in each of four cells.
When known prior art processors are used in this application, an FFT processor is required for each pair of range cells since the FFT processor has only a 6 MHz complex data rate. One version of the processor in the present invention, however, is capable of processing data at a 24 MHz real data rate with less hardware than the known prior art FFT mechanizations required to process at a 12 MHz real data rate.
The foregoing and other dramatic improvements in the art of spectral analysis of signals are provided in the signal processor and method according to the present invention which utilizes novel data manipulation and processing techniques in conjunction with the most desirable aspects of the foregoing techniques to eliminate the need for complex multipliers in each processor stage, to eliminate the need for complex phase shifters or twiddle factor multipliers between each stage, and to minimize the number of multipliers in the processor and the number of multiplications the processor must perform.
These and other advantages and novel features of the present invention will become apparent to those skilled in the art from the following detailed description of the present invention when considered in conjunction with the accompanying drawings.